package algocasts;

import java.util.TreeMap;

public class P93_SlidingWindowMaximum {
    // Time: O(k*n) Space: O(1)
    public int[] maxSlidingWindow_BruteForce(int[] nums, int k) {
        if (nums == null || nums.length == 0) return nums;
        int n = nums.length;
        int[] res = new int[n - k + 1];
        for (int left = 0; left <= n - k; left++) {
            int max = nums[left];
            for (int i = left; i < left + k; i++) max = Math.max(max, nums[i]);
            res[left] = max;
        }
        return res;
    }

    // Time: O(n*log(k))  Space: O(k)
    public int[] maxSlidingWindow_TreeMap(int[] nums, int k) {
        if (nums == null || nums.length == 0) return nums;
        int n = nums.length, p = 0;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < k; i++) map.put(nums[i], i);
        int[] res = new int[n - k + 1];
        res[p++] = map.lastKey();
        for (int i = k; i < n; i++) {
            if (map.get(nums[i - k]) == i - k) map.remove(nums[i - k]);
            map.put(nums[i], i);
            res[p++] = map.lastKey();
        }
        return res;
    }

    // Time: O(n)  Space: O(n)
    public int[] maxSlidingWindow_On(int[] nums, int k) {
        if (nums == null || nums.length == 0) return nums;
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int[] maxFromLeft = new int[n];
        int[] maxFromRight = new int[n];
        maxFromLeft[0] = nums[0];
        maxFromRight[n - 1] = nums[n - 1];
        for (int i = 1, j = n - 2; i < n; i++, j--) {
            maxFromLeft[i] = i % k == 0 ? nums[i] : Math.max(nums[i], maxFromLeft[i - 1]);
            maxFromRight[j] = j % k == k - 1 ? nums[j] : Math.max(nums[j], maxFromRight[j + 1]);
        }
        for (int i = 0; i <= n - k; i++)
            res[i] = Math.max(maxFromRight[i], maxFromLeft[i + k - 1]);
        return res;
    }

}
